#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int n,k,lim,a[N],ans;
vector<int> v[N];
struct node{
	int siz,tag[4],sum[16];
}t[N<<2];
inline void pushup(int u){
	for(int i=0;i<lim;i++)
		t[u].sum[i]=0;
	int now=0;
	for(int i=0;i<k;i++)
		if(t[u].tag[i]) now|=1<<i;
	if(t[u].siz==1) t[u].sum[now]=1;
	else{
		for(int i=0;i<lim;i++)
			t[u].sum[i|now]+=t[u<<1].sum[i]+t[u<<1|1].sum[i];
	}
}
inline void maketag(int u,int p,int x){
	t[u].tag[p]+=x;
	pushup(u);
}
inline void build(int u,int l,int r){
	t[u].siz=r-l+1;
	if(l==r){
		t[u].sum[0]=1;
		return;
	}
	int mid=(l+r)>>1;
	build(u<<1,l,mid),build(u<<1|1,mid+1,r);
}
inline void update(int u,int l,int r,int L,int R,int p,int x){
	if(l>=L&&r<=R) maketag(u,p,x);
	else{
		int mid=(l+r)>>1;
		if(L<=mid) update(u<<1,l,mid,L,R,p,x);
		if(R>mid) update(u<<1|1,mid+1,r,L,R,p,x);
		pushup(u);
	}
}
inline void work(vector<int> v,int x){
	int siz=v.size();
	for(int i=siz-1;i>=0;i--){
		if(siz-i>k) break;
		int nxt=0;
		if(i>0) nxt=v[i-1];
		update(1,1,n,nxt+1,v[i],siz-i-1,x);
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	freopen("reporter.in","r",stdin);
	freopen("reporter.out","w",stdout);
	cin>>n>>k;
	lim=1<<k;
	build(1,1,n);
	for(int i=1;i<=n;i++){
		cin>>a[i];
		work(v[a[i]],-1);
		v[a[i]].push_back(i);
		work(v[a[i]],1);
		ans+=t[1].sum[lim-1];
	}
	cout<<ans;
	return 0;
}
